Prof. Boris Melnikov
Shenzhen MSU – BIT University, China
Title: On the non-existence of a simple version of the polynomial algorithm for extracting the root from the language
Abstract:
For the usual operation of concatenation of words considered as multiplication, the concatenation of languages is obviously determined, and on the basis of the last operation, the degree of the language and the root of a given degree (if available) is determined.
When describing algorithms for constructing a language that is a root of degree M from a given language, so called potential roots are of great importance: these are the words (not the languages) whose considered M-th degree is included in a given language. It is easily to show that all potential roots for a given language are constructed using a polynomial algorithm.
This task, apparently, is not simplified when considering words and languages over the 1-letter alphabet, which is done in this paper.
So called taboo pair of potential roots is a pair whose word concatenation is not included in the language. In previous publications on the topic of describing algorithms for extracting roots from a language, the hypothesis arose that a polynomial algorithm for extracting a root from a language can be described on the basis of considering the set of taboo pairs only, by iterating over specially described subsets of the set of potential roots.
This paper shows, that such an algorithm (called “simple”) is impossible, i.e., if there is a polynomial algorithm for extracting the root from the language, then this algorithm must use some additional information.
Biography:
In 1979, I graduated from the Physics and Mathematics School at Moscow State University (currently Kolmogorov Mathematical School).From 1979 to 1984, I studied at Moscow State University (Faculty of Computational Mathematics and Cybernetics).Further, until 1992, I worked as a programmer at a scientific research institute, and since 1988, I simultaneously studied in correspondence postgraduate study at Moscow State University.In 1990, I defended my first dissertation (PhD), also at Moscow State University.Soon I began working at the Ulyanovsk Branch of Moscow State University, which was subsequently transformed into an independent university.At this university, I went through all the "steps" from assistant to professor, head of department; at the same time in 1997, I defended the "second Russian" dissertation (doctoral thesis, "Habilitation").
From 2003 to 2016, I worked at two other universities of Volga Region (Togliatti and Samara).In them, I was the Chairman of the Dissertation Council for 5 years, and the chief editor of a scientific electronic journal for 3 years.In 2016, I returned to Moscow, where I worked simultaneously in Moscow State University and Russian State Social University.In 1998-2014, I was 12 times the visiting professor at leading universities of Europe (including ETH-Zurich 3 times).In 1999-2019, I was scientific adviser of 13 candidates of sciences (PhD) already defended.I have about 40 presentations at international conferences outside Russia and about 100 international conferences in Russia.Since 2018, I have been working in China; I am Professor of Shenzhen MSU-BIT University.
Fields of my scientific interests: artificial intelligence and programming nondeterministic games; heuristic algorithms; discrete optimization problems; mathematical modeling; DNA sequence processing algorithms; nondeterministic finite automata and regular languages; non-traditional variants for setting context-free languages; semigroup algebra.